from typing import List


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        result = 0
        heights = [0 for _ in range(len(matrix[0]))]
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                heights[col] = 0 if matrix[row][col] == '0' else heights[col] + 1

            heights_ext = heights + [0]
            stack = []
            areas = [0] * len(heights_ext)
            for right, h in enumerate(heights_ext):
                while stack and heights_ext[stack[-1]] >= h:
                    left = stack.pop()
                    areas[left] += (right-left-1) * heights_ext[left]
                left = stack[-1] if stack else -1
                areas[right] = h * (right - left)
                stack.append(right)
            result = max(result, max(areas))
        return result




import numpy as np
def brutal_solve(matrix):
    if len(matrix) == 0:
        return 0

    matrix = [[int(c) for c in row] for row in matrix]
    matrix = np.asarray(matrix, dtype=np.int32)
    n_rows = len(matrix)
    if n_rows == 0:
        return 0
    n_cols = len(matrix[0])

    result = 0
    for row0 in range(n_rows):
        for row1 in range(row0, n_rows):
            for col0 in range(n_cols):
                for col1 in range(col0, n_cols):
                    area = (row1-row0+1) * (col1-col0+1)
                    if area > result and matrix[row0: row1+1, col0: col1+1].sum() == (row1-row0+1) * (col1-col0+1):
                        result = area
    return result


def test():
    import random
    for i in range(10000):
        n_rows = random.randint(0, 5)
        n_cols = random.randint(1, 5)
        matrix = [['' for _ in range(n_cols)] for _ in range(n_rows)]
        for row in range(n_rows):
            for col in range(n_cols):
                v = random.randint(0, 10)
                matrix[row][col] = str(int(bool(v)))
        res1 = Solution().maximalRectangle(matrix)
        res2 = brutal_solve(matrix)
        if res1 != res2:
            print(matrix, res1, res2)
test()

